# -*- coding:utf-8 -*-
class TreeLinkNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None
class Solution:
    def GetNext(self, pNode):
        # write code here

        if pNode.right:
            pNode=pNode.right
            while pNode.left!=None:
                pNode=pNode.left
        else:
            if not pNode.next:
                return None
            else:
                if  pNode.next.left==pNode:
                        pNode=pNode.next

                elif  pNode.next.right==pNode:
                    while pNode.next and pNode.next.right==pNode:
                        pNode=pNode.next
                    if pNode.next:
                        pNode=pNode.next
                    else:
                        return None

        return pNode













       

tree = TreeLinkNode(1)
